#include <stdio.h>
#include <conio.h>

void quicksort(int arr[], int low, int high); 
int partition(int arr[], int low, int high); 

int main() { 
    int a[100], i, n; 
    printf("Enter number of array elements: \n"); 
    scanf("%d", &n); 
    printf("Enter array elements: \n"); 
    for(i = 0; i < n; i++) { 
        scanf("%d", &a[i]); 
    } 
    printf("Before sorting, array elements are: \n"); 
    for(i = 0; i < n; i++) { 
        printf("%d\n", a[i]); 
    } 
    quicksort(a, 0, n - 1); 
    printf("After sorting, array elements are: \n"); 
    for(i = 0; i < n; i++) { 
        printf("%d\n", a[i]); 
    } 
} 

void quicksort(int arr[], int low, int high) { 
    int j; 
    if(low < high) { 
        j = partition(arr, low, high); 
        quicksort(arr, low, j - 1); 
        quicksort(arr, j + 1, high); 
    } 
} 

int partition(int a[], int low, int high) { 
    int i, j, pivot, temp; 
    i = low + 1; 
    j = high; 
    pivot = a[low]; 
    while(1) { 
        while(i <= high && a[i] < pivot) { 
            i++; 
        } 
        while(j > low && a[j] > pivot) { 
            j--; 
        } 
        if(i < j) { 
            temp = a[i]; 
            a[i] = a[j]; 
            a[j] = temp; 
        } else { 
            break; 
        } 
    } 
    a[low] = a[j]; 
    a[j] = pivot; 
    return j; 
}